//
//  AVLTree.hpp
//  AVLtree
//
//  Created by 卜绎皓 on 2022/11/16.
//

#pragma once
#include<iostream>
#include<assert.h>
#include<string>
using namespace std;
 
 
template<class K,class V>
struct AVLTreeNode
{
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;//定义成三叉链的形式
    int _bf;//balance factor平衡因子
    pair<K, V> _kv;//用pair同时存K和V两个数据
 
    AVLTreeNode(const pair<K,V>& kv)//节点构造函数
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_bf(0)//平衡因子初始给0
        ,_kv(kv)
    {}
};
 
template<class K,class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    AVLTree()
        :_root(nullptr)
    {}
    //拷贝构造和赋值拷贝也需要自己实现
    AVLTree(const AVLTree<K,V>& kv)
    {
        _root = Copy(kv._root);
    }
    AVLTree<K, V>& operator=(AVLTree<K,V> kv)
    {
        swap(_root, kv._root);
        return *this;
    }
    ~AVLTree()
    {
        Destroy(_root);
        _root = nullptr;
    }
    Node* Copy(Node* root)
    {
        if (root == nullptr)
            return nullptr;
        Node* newroot = new Node(root->_key);//建立新节点
        newroot->_left = Copy(root->_left);//新节点的左右节点再去转换成子问题
        newroot->_right = Copy(root->_right);
        return newroot;//最后返回新节点
    }
    void Destroy(Node* root)
    {
        //利用后序遍历去释放节点
        if (root == nullptr)
        {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }
    V& operator[](const K& key)//重载operator[]
    {
        //operator[]的原则是:
        //如果插入成功返回插入都value的引用
        //如果插入失败则返回V类型默认缺省值
        pair<Node*, bool> ret = Insert(make_pair(key, V()));//V采用传匿名对象的方式
        return ret.first->_kv.second;
    }
    Node* Find(const pair<K, V>& kv)//查找函数
    {
        Node* cur = _root;
        while (cur)
        {
            if (kv.first > cur->_kv.first)
            {
                cur = cur->_right;
            }
            else if (kv.first < cur->_kv.first)
            {
                cur = cur->_left;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }
    void RotateR(Node* parent)//右单旋
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
 
        parent->_left = subLR;
        if (subLR != nullptr)//注意:这里一定要判断不为空的，因为下面可能会出现空指针的解引用
        {
            subLR->_parent = parent;
        }
        subL->_right = parent;
        Node* parentParent = parent->_parent;//一定要在改变链接关系之前把这个指针存下来
        parent->_parent = subL;
        
        //if (parentParent == nullptr)或者采用这个条件也是可以的
        if(parent==_root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            //这里注意:parent还有父母时，链接之前需要注意判断到底是右孩子还是左孩子
            if (parentParent->_left == parent)
                parentParent->_left = subL;
            else
                parentParent->_right = subL;
 
            subL->_parent = parentParent;//最后还要把父指针关系链接上
        }
 
        parent->_bf = subL->_bf = 0;//最后右单旋完成后平衡因子都要修改成0
    }
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
 
        //先把subR的左孩子赋值给parent的右节点
        parent->_right = subRL;
        if (subRL != nullptr)//注意一定要判断是否为空的情况
        {
            subRL->_parent = parent;//然后链接parent指针
        }
 
        //然后subR的左节点链接上parent
        subR->_left = parent;
        Node* parentParent = parent->_parent;//提前记录
        parent->_parent = subR;
        //if (parentParent == nullptr)
        if (parent == _root)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else
        {
            if (parentParent->_left == parent)
                parentParent->_left = subR;
            else
                parentParent->_right = subR;
 
            subR->_parent = parentParent;
        }
 
        parent->_bf = subR->_bf = 0;
    }
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;//注意：需要提前存subRL的平衡因子，因为旋转可能引起改变
        //subRL的平衡因子是双旋的关键节点
 
        RotateR(parent->_right);//先进行右旋，并注意旋转点为父节点的右节点
        RotateL(parent);//再进行左旋，此时旋转点为父节点
 
        if (bf == 0)
        {
            parent->_bf = 0;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else if (bf == 1)
        {
            parent->_bf = -1;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else if (bf == -1)
        {
            parent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        }//注意这里处理完成过后sunRL的平衡因子一定都是等于0的
        else
        {
            assert(false);
        }
    }
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;
        RotateL(parent->_left);//先进行左旋，并注意旋转点为父节点的左节点
        RotateR(parent);//再进行右旋，此时旋转点为父节点
 
        if (bf == 0)
        {
            parent->_bf = 0;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        else if (bf == 1)
        {
            parent->_bf = 0;
            subL->_bf = -1;
            subLR->_bf = 0;
        }
        else if (bf == -1)
        {
            parent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        }//注意这里处理完成过后sunRL的平衡因子一定都是等于0的
        else
        {
            assert(false);
        }
    }
    pair<Node*,bool> Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)//根节点为空时先new一个新节点
        {
            _root = new Node(kv);
            return make_pair(_root, true);
        }
 
        Node* cur = _root;
        Node* parent = nullptr;
        //先利用while循环去找cur的空位
        while (cur)
        {
            if (kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return make_pair(cur, false);
            }
        }
        //将cur插入到相应位置
        cur = new Node(kv);
        Node* newnode = cur;//用一个newnode记录一下新节点用以返回
        if (kv.first > parent->_kv.first)
        {
            parent->_right = cur;//注意三叉链的链接逻辑顺序,等号左右方向不能反，先把cur链接到父节点的右边
            cur->_parent = parent;//然后再去把父指针知道父节点
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
 
        //进行旋转调整
        //while(cur!=_root)
        while (parent)
        {
            //1.进入循环先对平衡因子进行调整
            if (cur == parent->_right)
            {
                parent->_bf++;
            }
            else
            {
                parent->_bf--;
            }
 
            //分三种情况向上走
            if (parent->_bf == 0)//平衡因子等于0不需要调整
            {
                //为什么不需调整
                //因为等于0的话，说明底层子树高度不平衡，添加进入新元素后平衡了，只要平衡了高度并没发生变化，不会影响上面的父节点
                break;
            }
            else if (parent->_bf == -1 || parent->_bf == 1)
            {
                //平衡因子等于-1，说明插入新节点后子树的高度不平衡了，需要继续往上迭代查看父节点是否还满足平衡节点
                cur = parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                if (parent->_bf == -2)//父节点等于-2，说明左边高，触发右旋的情况
                {
                    if (cur->_bf == -1)//cur节点等于-1，说明在cur的左边更高，触发右单旋的情况
                    {
                        RotateR(parent);
                    }
                    else//cur等于-1,说明在cur的右边更高，触发左右双旋
                    {
                        RotateLR(parent);
                    }
                }
                else//父节点等于1，说明右边更高，触发左旋的情况
                {
                    if (cur->_bf == 1)//cur节点等于1时，说明在cur的右边更高，触发右单旋的情况
                    {
                        RotateL(parent);
                    }
                    else//cur等于-1,说明在cur的左边更高，触发右左双旋
                    {
                        RotateRL(parent);
                    }
                }
                //思考：为什么上面在传参数的时候，都是传parent的节点呢？这样的好处是什么呢
 
                break;//调整完成后break退出循环
                //这里为什么调整完成过后就可以退出，通过旋转调整平衡因子后，parent节点的平衡因子都为0了，调整过后不需要再向上继续查找了
            }
            else
            {
                assert(false);
            }
        }
        return make_pair(newnode,true);
    }
    void _Inorder(Node* root)//中序遍历打印每个节点
    {
        if (root == nullptr)
            return;
        _Inorder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _Inorder(root->_right);
    }
    void Inorder()
    {
        _Inorder(_root);
        cout << endl;
    }
 
    //验证是否为平衡二叉树
    //1.左子树高度与右子树高度差必须小于1
    int _Height(Node* root)//求树的高度函数
    {
        if (root == nullptr)
        {
            return 0;
        }
 
        int leftHeight = _Height(root->_left);//递归去子问题求解
        int rightHeight = _Height(root->_right);
 
        return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
    }
    bool _IsBalance(Node* root)
    {
        if (root == nullptr)
        {
            return true;
        }
 
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
 
        // 2.检查一下每颗树的平衡因子是否正确
        if (rightHeight - leftHeight != root->_bf)
        {
            cout << "平衡因子异常:" << root->_kv.first << endl;
            return false;
        }
 
        return abs(rightHeight - leftHeight) < 2
            && _IsBalance(root->_left)
            && _IsBalance(root->_right);//分别递归到各自的左右子树再去检查
    }
    bool IsAVLTree()
    {
        return _IsBalance(_root);
    }
private:
    Node* _root;
};
